Теорема Хивуда

Хроматическое число любого планарного графа не превосходит 5.

Пусть $G$ — обыкновенный планарный граф с $n$ вершинами, а $\Gamma$ — его правильное изображение. Доказательство проведём индукцией по $n$. База индукции при $n=1$ очевидна. Шаг индукции. Пусть утверждение верно для всех планарных графов с менее чем $n > 1$ вершинами. По лемме о планарных графах, в $G$ существует вершина $v$ такая, что $\text{deg}(v) \leq 5$. Рассмотрим граф $G-v$. По предположению индукции, он имеет правильную 5-раскраску $f$. Если степень вершины $v$ меньше 5, то её соседи окрашены не более чем в 4 цвета. Тогда для $v$ найдется свободный цвет, и мы можем дополнить раскраску $f$ до правильной 5-раскраски всего графа $G$. Рассмотрим случай, когда $\text{deg}(v) = 5$, и все соседи $v$ окрашены в 5 различных цветов. Обозначим соседей $v_1, v_2, v_3, v_4, v_5$ в порядке их следования по часовой стрелке в изображении $\Gamma$. Пусть $f(v_i) = i$ для $i = 1, \dots, 5$. Рассмотрим $G_{1,3}$ — подграф графа $G$, порождённый всеми вершинами, окрашенными в цвета 1 и 3. Возможны два случая. **Случай 1:** Вершины $v_1$ и $v_3$ лежат в разных компонентах связности графа $G_{1,3}$. Пусть $K$ — компонента связности $G_{1,3}$, содержащая $v_1$. Переопределим раскраску $f$ на вершинах из $K$, поменяв цвета 1 и 3 местами. Новая раскраска $f'$ будет правильной раскраской графа $G-v$. В ней вершина $v_1$ получит цвет 3, как и вершина $v_3$. Таким образом, среди соседей $v$ ни одна вершина не будет окрашена в цвет 1. Следовательно, мы можем покрасить вершину $v$ в цвет 1, получив правильную 5-раскраску графа $G$. **Случай 2:** Вершины $v_1$ и $v_3$ лежат в одной компоненте связности графа $G_{1,3}$. Это означает, что в $G$ существует $(v_1, v_3)$-путь, все вершины которого окрашены в цвета 1 и 3. Добавив к этому пути рёбра $(v, v_1)$ и $(v, v_3)$, мы получим простой цикл $C$. В правильном изображении $\Gamma$ этот цикл $C$ разделяет плоскость на две области — внутреннюю и внешнюю. Поскольку вершины $v_1, \dots, v_5$ расположены вокруг $v$ по часовой стрелке, вершины $v_2$ и $v_4$ окажутся в разных областях, разделённых циклом $C$. Теперь рассмотрим $G_{2,4}$ — подграф графа $G$, порождённый всеми вершинами, окрашенными в цвета 2 и 4. Вершины $v_2$ и $v_4$ не могут лежать в одной компоненте связности $G_{2,4}$. Если бы они лежали, то существовал бы $(v_2, v_4)$-путь, состоящий только из вершин цветов 2 и 4. Изображение этого пути в $\Gamma$ должно было бы пересечь изображение цикла $C$, чтобы соединить $v_2$ и $v_4$. Но так как $G$ планарен, рёбра могут пересекаться только в вершинах. Однако вершины цикла $C$ (кроме $v$) окрашены в цвета 1 и 3, а вершины $(v_2, v_4)$-пути — в цвета 2 и 4, поэтому у них нет общих вершин. Это приводит к противоречию. Следовательно, $v_2$ и $v_4$ лежат в разных компонентах связности графа $G_{2,4}$. По аналогии со случаем 1, мы можем перекрасить компоненту связности $G_{2,4}$, содержащую $v_2$, поменяв цвета 2 и 4 местами. В новой раскраске $f''$ графа $G-v$ вершина $v_2$ будет иметь цвет 4. Тогда среди соседей $v$ не останется вершин цвета 2. Положив $f''(v) = 2$, мы получим правильную 5-раскраску графа $G$. $\square$